package Stack;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 *  题目:小行星碰撞
 *  题目简述 ：
 *  给定一个整数数组 asteroids，表示在同一行的小行星。
 * 对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。
 * 找出碰撞后剩下的所有小行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。
 *
 */
public class OfferP37 {
    /**
     * 核心思想 ：
     * (1)遍历数组中的所有元素，若是所要压入栈中的元素 >=0 时，即不可能出现碰撞的情况，直接继续遍历数组即可；
     *（2）若不满足1中的条件，即需要遍历栈顶元素，循环结束条件 ： 栈顶元素和所插入的元素不会发生碰撞；
     *   1. 若是栈为空，或者栈顶元素为负，即可直接向栈中压入元素；
     *   2.栈顶元素 + 所插入元素的值 == 0 时，弹栈，同时结束循环；
     *   3.栈顶元素 + 所插入元素的值 < 0 时,弹栈，继续进行循环；
     *   4.栈顶元素 + 所插入元素的值 > 0 时,放弃此元素，同时结束循环
     * @param asteroids
     * @return
     */

    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> stack = new LinkedList<>();
        // 由于是链表结构，所以会出现，在转数组的过程中，倒序
        int addResult;
        for (int asteroid : asteroids) {
            // 由于所插入的元素不会发生变化，当所插入栈中的星球大于等于零时（即，星球向右移动）
            // 无论栈顶元素的正负，直接向栈中插入元素即可（不可能发生星球碰撞情况）
            if (asteroid >= 0){
                stack.push(asteroid);
                continue;
            }
            // 循环遍历栈顶元素，直至不会碰撞为止
            while(true) {

                // （1）栈为空
                // （2）栈顶元素小于等于零（即，星球向左移动）
                //  即，不会出现星球碰撞的情况  ===》 直接向栈中插入元素即可
                if (stack.isEmpty() || stack.peek() <= 0) {
                    //  由于栈顶元素会发生变化，即每次都需要对于栈顶元素进行判断
                    stack.push(asteroid);
                    break;
                }
                addResult = stack.peek() + asteroid;
                if (addResult < 0) { // 即，当栈顶元素与数组中元素相加为零时，获取下一个数组元素与栈顶元素进行比较
                    stack.pop();
                    continue;
                }
                else if(addResult == 0){
                    stack.pop();
                }
                break;
            }
        }
        for (Integer integer : stack) {
            System.out.println(integer);
        }
        // Integer集合转化为Integer数组
//        Integer[] integers = stack.toArray(new Integer[stack.size()]);
        // Integet数组转化为int数组
//        int[] results = Arrays.stream(integers).mapToInt(Integer::valueOf).toArray();
//        return results;
        return stack.stream().mapToInt(i->i).toArray();
    }
}
